package march.test_3_27;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> l= new ArrayList<>();
        l.add(0,0);
        list.add(0, l);
        ArrayList<Integer> l2 = new ArrayList<>();
        l2.add(0,1);
        list.add(1,l2);
        for(int i = 2; i < 91; i++) {
            ArrayList<Integer> a1 = list.get(i-1);
            ArrayList<Integer> a2 = list.get(i-2);
            list.add(i,result(a1,a2));
        }
        System.out.println("hao");
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            ArrayList<Integer> read = list.get(n);
            for (int i = 0; i < read.size(); i++) {
                System.out.print(read.get(i));
            }
            System.out.println();
        }
    }
    public static ArrayList<Integer> result(ArrayList<Integer> a1,ArrayList<Integer> a2) {
        int s1 = a1.size();
        int s2 = a2.size();
        ArrayList<Integer>  arrayList = new ArrayList<>();
        for(int i = 0; i < s1 && i < s2; i++) {
            int count = a1.get(i) + a2.get(i);
            if(count > 9) {
                if(arrayList.size() == i + 1) {
                    arrayList.add(i,count % 10 + arrayList.get(i));
                } else {
                    arrayList.add(i,count / 10);
                }
                arrayList.add(i + 1,1);
            } else if(count == 9 && arrayList.size() == i + 1){
                arrayList.add(i,1);
                arrayList.add(i + 1,1);
            } else if(arrayList.size() == i + 1) {
                arrayList.add(i,count + 1);
            } else {
                arrayList.add(count);
            }
        }
        if(s1 > s2) {
            for (int i = s2; i < s1; i++) {
                int count = a1.get(i);
                if(arrayList.size() == i + 1) {
                    count += arrayList.get(i);
                }

                if( count > 9) {
                    arrayList.add(i + 1,1);
                }
                if (arrayList.size() == i + 1) {
                    arrayList.add(i,count % 10 + arrayList.get(i));
                } else {
                    arrayList.add(i,count % 10 );
                }

            }
        } else {
            for (int i = s1; i < s2; i++) {
                int count = a2.get(i);
                if(arrayList.size() == i + 1) {
                    count += arrayList.get(i);
                }
                if( count > 9) {
                    arrayList.add(i + 1,1);
                }
                if (arrayList.size() == i + 1) {
                    arrayList.add(i,count % 10 + arrayList.get(i));
                } else {
                    arrayList.add(i,count % 10 );
                }
            }
        }
        return arrayList;
    }
}
